/**
 * Created by zhourh on 2018/8/2.
 */
public class ConstructQuadTree {

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {1,1,1,1,0,0,0,0},
                {1,1,1,1,0,0,0,0},
                {1,1,1,1,1,1,1,1},
                {1,1,1,1,1,1,1,1},
                {1,1,1,1,0,0,0,0},
                {1,1,1,1,0,0,0,0},
                {1,1,1,1,0,0,0,0},
                {1,1,1,1,0,0,0,0}};

        Node node = new ConstructQuadTree().construct(grid);

        System.out.println(node);

        int[][] grid2 = new int[][]{
                {1,1,0,0,0,0,0,0},
                {1,1,0,0,0,0,0,0},
                {1,1,0,0,0,0,1,1},
                {1,1,0,0,0,0,1,1},
                {0,0,0,0,0,0,1,1},
                {0,0,0,0,0,0,1,1},
                {1,1,1,1,1,1,0,0},
                {1,1,1,1,1,1,0,0}};

        Node node2 = new ConstructQuadTree().construct(grid2);

        System.out.println(node2);
    }


    public Node construct(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return null;
        }

        int height = grid.length;
        int width = grid[0].length;
        return construct(grid, 0, 0, width - 1, height - 1);

    }


    public Node construct(int[][] grid, int left, int top, int right, int bottom ) {

        if (left > right || top > bottom) {
            return null;
        }

        int sum = 0;
        for (int row = top; row <= bottom; row++) {
            for (int column = left; column <= right; column++) {
                sum += grid[row][column];
            }
        }

        if (sum == 0) {
            return new Node(false, true, null, null, null, null );
        } else if (sum == (right - left + 1) * (bottom - top + 1)) {
            return new Node(true, true, null, null, null, null);
        } else {
            Node topLeftNode = construct(grid, left, top, (right + left) / 2, (bottom + top) / 2);
            Node topRightNode = construct(grid, (right + left) / 2 + 1, top, right, (bottom + top) / 2);
            Node bottomLeftNode = construct(grid, left, (bottom + top) / 2 + 1, (right + left) / 2, bottom);
            Node bottomRightNode = construct(grid, (right + left) / 2 + 1, (bottom + top) / 2 + 1, right, bottom);
            return new Node(true, false, topLeftNode, topRightNode, bottomLeftNode, bottomRightNode);
        }
    }

    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;

        public Node() {}

        public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
            val = _val;
            isLeaf = _isLeaf;
            topLeft = _topLeft;
            topRight = _topRight;
            bottomLeft = _bottomLeft;
            bottomRight = _bottomRight;
        }
    }


}

